package dp.longestValidParentheses;

import java.util.HashMap;

/**
 * @Date 2020/05/09
 * @author 王光浩
 * @Thinking 使用 DP
 * @Method 
 * 	使用一个 Map 存储每一个以 ‘）’结尾的最长有效括号长度，key 为 ')'下标，value 为最长长度
 * 	使用 leftP 表示未被匹配的 '(' 的个数
 *  使用 ret 表示字符串 s 中最长有效括号的长度
 *  解题方法如下：
 *  	（1）遍历字符串，如果当前下标 i 对应字符是 '(' 则进入步骤 （2），否则进入步骤 （3）
 *  	（2）将 leftP 自增一个，进入步骤（1）
 *  	（3）如果 leftP 值大于 0 ，则进入步骤 （4），否则进入步骤 （1）
 *  	（4）在 map 中我们存储了所有以 ')' 为结尾的最长有效括号长度，我们存储了对应的 ')' 的
 *  		 下标和对应的最长有效长度。 如果我们 想要获取 i 对应的最长有效括号长度，我们需要做一个
 *  		 拼接工作，首先获取对应下标 i ')' 的 '(' 的位置，获取这两个括号之间的有效括号长度；
 *  		 然后在获取在 （...）之前的与 (...) 向连接的所有有效括号长度，将获取的总长度保存在 count中
 *          ，将 leftP 自减 1。将 ret 与 count 进行比较，将较大者赋给 ret。
 * @Analysis 时间复杂度O（n^2），空间复杂度O（n）
 */
public class MyMethodOne {
	public int longestValidParentheses(String s) {
		if (s == null || s.length() <= 1)
			return 0;
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		int leftP = 0;
		int ret = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(') {
				leftP++;
			} else if (leftP > 0) {
				int index = i;
				int count = 2; // 统计以该 ‘）’为结尾的最长有效括号
				// 统计在该 ‘）’内部的最长有效括号长度
				while (map.containsKey(index - 1)) {
					count += map.get(index - 1);
					index -= map.get(index - 1);
				}
				// 统计在该 ‘）’之外的有效括号长度
				index -= 1;
				while (map.containsKey(index - 1)) {
					count += map.get(index - 1);
					index -= map.get(index - 1);
				}
				leftP--;
				ret = Math.max(ret, count);
				map.put(i, count);
			}
		}
		return ret;
	}
}
